In cryptography, e.g. public key cryptography, operations such as multiplication or exponentiation of integers in some group Zn may be required, where modular arithmetic is used to operate on the integers. For example, to multiply two numbers modulo some n, the classical approach is to first perform the multiplication and then calculate the remainder. Although the classical approach is simple for basic operations such as in multi-precision calculations and does not require precomputation, the step of calculating the remainder is considered slow. The calculation of the remainder is referred to as reduction in modular arithmetic.
Modular reduction is often employed in cryptographic applications. Of the well known methods for modular reduction, the most commonly used is the method of Montgomery modular reduction, referred to as Montgomery reduction in short. Montgomery reduction avoids the expensive division operations typically used in classical modular reduction. Montgomery reduction benefits from the fact that steps of multiplication and shifting are generally faster than division on most computing machines. Montgomery reduction relies on performing certain precomputations and, by doing so, many calculations can be done faster. Also, as opposed to classical methods of reduction-from-above such as Euclidean division, Montgomery reduction reduces from below, that is, the method proceeds by clearing the least-significant portions of the unreduced quantity, leaving the remainder in the upper portion.
In Montgomery reduction, calculations with respect to a modulus n are carried out with the aid of an auxiliary number R called the Montgomery radix or base. When the modulus is a prime number, a good choice of radix is 2 to some exponent, typically chosen as the first convenient power of 2 larger than the modulus. In the following, the exponent of 2 is denoted by L so that R=2L. The Montgomery reduction of a number a with radix R and prime modulus n is the quantity given by aR−1 mod n. The Montgomery multiplication of two numbers is the Montgomery reduction of their product, written as ab=abR−1 mod n. Calculations are carried out on numbers in their Montgomery form. The Montgomery form of a number a is defined â=aR mod n. Conversion to Montgomery form may be carried out via Montgomery multiplication where â=aR2=aR mod n. Conversion from Montgomery form back to regular form may be carried out by the Montgomery reduction: âR−1 mod n=a mod n, or by the Montgomery multiplication: â1=aRR−1=a mod n.
In a given cryptographic system, a computational engine may be used for calculating the Montgomery product of two numbers, this engine being sometimes referred to as a Montgomery engine or Montgomery machine. The engine may be implemented in a hardware or software module and operates on a set of parameters to produce a result. For example, the engine may be used to produce the result ab on inputs a and b. The Montgomery engine can also be configured to convert to and from Montgomery form. To convert to Montgomery form, the engine accepts a and R2 as inputs and produces an output â. Conversely, for converting back to normal form, the engine accepts â and 1 as inputs and outputs a. The engine may also be configured to calculate the Montgomery reduction of a number. In this case, the engine accepts a and 1 as inputs and produces aR−1 mod n as an output. To initialize the Montgomery engine, the engine is loaded with a modulus n and a radix R.
The use of Montgomery reduction as a component of Montgomery multiplication is well known. There are many algorithms that can be used to perform the Montgomery multiplication. In one example, the Montgomery multiplication of two k-digit integers a and b in base 2w, reduced mod an k-digit integer n, where a=(ak−1 . . . a1a0), b=(bk−1 . . . b1b0), n=(nk−1 . . . n1n0) where each component is written base 2w, and 0≦a,b<n, produces an output abR−1 mod n. Multi-precision values are typically expressed in base 2w form, where w is the wordsize of the machine in bits. In this example, R=2L as above, and an additional precomputed value, μ=−n−1 mod 2w, is also used in the reduction. In one exemplary algorithm. Montgomery multiplication may proceed as follows:
1. c←0, where c will hold the result abR−1 mod n and c=(ckck−1 . . . c1c0).
2. For i from 0 to (k−1) do the following:
2.1 m←(c0+ai,b0)μ mod 2w; and
2.2 c←(c+aib+mn)/2w.
3. If c≧n then c←c−n.
4. Return (c).
The implementation of Montgomery multiplication is a fundamental operation on values in Montgomery representation. Step 3 can leak information about quantities under computation and is therefore sometimes omitted, in which case the output quantity is not fully reduced. As can be appreciated, efficiency may be increased by pre-computing certain fixed values to be used in the calculations. Such values include μ=(−n)−1 mod 2w, for some w typically being the bit size of a word (or block) of the value (or perhaps the entire value) being operated on; and R2 mod n. In this example, the multiplication of a and b have been interleaved with the Montgomery reduction. In the next example, we will consider directly performing Montgomery reduction on a value a.
In Montgomery reduction, the value μ is used to zero w least significant bits of a value a. First, a multiplier m=μa mod2w is computed. The value m has at most w bits. Adding a+mn will zero w least significant bits of a, and a may be shifted down w bits. Since typically L=kw, where k is the number of w-bit words in R; this operation is repeated k times to effect the Montgomery reduction aR−1 mod n.
Often, a also results from a multiplication operation and, therefore, is twice the size of the modulus n. Alternatively, multiplication can be implemented by interleaving the expansion of multiplication with Montgomery reduction, as in the previous example.
In a register-based processor, registers are typically used to hold components of the value to be reduced, namely the precomputed value μ and the modulus n.